/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   BST_basic.h                                        :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: TYTY000 <767280080@qq.com>                 +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2024/04/24 11:00:27 by TYTY000           #+#    #+#             */
/*   Updated: 2024/04/25 20:21:45 by TYTY000          ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#ifndef __BST_BASIC__
#define __BST_BASIC__

#include <cstdlib>
#include <iostream>
template <typename T> BinNodePosi<T> &BST<T>::search(const T &e) {
  if (!BST<T>::_root || e == BST<T>::_root->data) {
    _s = nullptr;
    return BST<T>::_root;
  }
  _s = BST<T>::_root;
  while (true) {
    BinNodePosi<T> &n = (e < _s->data) ? _s->lc : _s->rc;
    if (!n || n->data == e)
      return n;
    _s = n;
    // return nullptr or nodeposi&  --> _s: a spot to insert....
  }
}

template <typename T> BinNodePosi<T> BST<T>::insert(const T &e) {
  BinNodePosi<T> &n = search(e);
  if (n)
    return n;
  n = new BinNode<T>(e, _s);
  ++BinTree<T>::_size;
  BinTree<T>::updateHeightAbove(n);
  return n;
}

template <typename T>
BinNodePosi<T> BST<T>::removeAt(BinNodePosi<T> &n, BinNodePosi<T> &s) {
  // n could be leaf, single child or double child.
  // need a var to store succ. data swap succ & n.
  BinNodePosi<T> w = n;       // 实际被摘除的节点，初值同x
  BinNodePosi<T> succ = NULL; // 实际被删除节点的接替者
  if (!HasLChild(*n))         // 若*x的左子树为空，则可
    succ = n = n->rc;         // 直接将*x替换为其右子树
  else if (!HasRChild(*n))    // 若右子树为空，则可
    succ = n = n->lc; // 对称地处理——注意：此时succ != NULL
  else { // 若左右子树均存在，则选择x的直接后继作为实际被摘除节点，为此需要
    w = w->succ(); // （在右子树中）找到*x的直接后继*w
    std::swap(n->data, w->data); // 交换*x和*w的数据元素
    BinNodePosi<T> u = w->parent;
    ((u == n) ? u->rc : u->lc) = succ = w->rc; // 隔离节点*w
  }
  s = w->parent; // 记录实际被删除节点的父亲
  if (succ)
    succ->parent = s; // 并将被删除节点的接替者与hot相联
  delete w;
  return succ; // 释放被摘除节点，返回接替者
  // BinNodePosi<T> succ = nullptr;
  // // Case 1: Node to be removed is a leaf (no children)
  // if (!n->lc && !n->rc) {
  //   s = n->parent; // Update the approximate target
  //   if (!s) {
  //     BST<T>::_root = nullptr;
  //   } else if (n == s->lc)
  //     s->lc = nullptr;
  //   else
  //     s->rc = nullptr;
  //   // delete n;
  //   return nullptr;
  // }

  // // Case 2: Node has two children (requires finding the in-order successor)
  // if (n->lc && n->rc) {
  //   BinNodePosi<T> succ = n->succ(); // Get the in-order successor
  //   n->data = succ->data;            // Swap data with the successor
  //   (succ->parent->lc == succ) ? succ->parent->lc = nullptr
  //                              : succ->parent->rc = nullptr;
  //   // delete succ;
  //   return n;
  // }

  // // Case 3: Node has only one child

  // succ = n->succ();     // Get the in-order successor
  // n->data = succ->data; // Swap data with the successor
  // if (succ->parent->lc == succ)
  //   succ->parent->lc = succ->rc; // Update parent's child pointer
  // else
  //   succ->parent->rc = succ->rc;
  // if (succ->rc)
  //   succ->rc->parent = succ->parent;
  // // delete succ;
  // return n;
}

template <typename T> bool BST<T>::remove(const T &e) {
  BinNodePosi<T> &n = search(e);
  if (!n)
    return false; // no target
  BST<T>::removeAt(n, _s);
  --BinTree<T>::_size;
  BinTree<T>::updateHeightAbove(_s);
  return true;
}
// template <typename T> BinNodePosi<T> BST<T>::connect34 (
//    BinNodePosi<T> a, BinNodePosi<T> b, BinNodePosi<T> c,
//    BinNodePosi<T> T0, BinNodePosi<T> T1, BinNodePosi<T> T2, BinNodePosi<T>
//    T3
// ) {
//    /*DSA*///print(a); print(b); print(c); printf("\n");
//    a->lc = T0; if ( T0 ) T0->parent = a;
//    a->rc = T1; if ( T1 ) T1->parent = a; this->updateHeight ( a );
//    c->lc = T2; if ( T2 ) T2->parent = c;
//    c->rc = T3; if ( T3 ) T3->parent = c; this->updateHeight ( c );
//    b->lc = a; a->parent = b;
//    b->rc = c; c->parent = b; this->updateHeight ( b );
//    return b; //¸Ã×ÓÊ÷ÐÂµÄ¸ù½Úµã
// }
// template <typename T> BinNodePosi<T> BST<T>::rotateAt( BinNodePosi<T> v ) {
// //vÎª·Ç¿ÕËï±²½Úµã
//    /*DSA*/if ( !v ) { printf ( "\a\nFail to rotate a null node\n" ); exit (
//    -1 ); } BinNodePosi<T> p = v->parent; BinNodePosi<T> g = p->parent;
//    //ÊÓv¡¢pºÍgÏà¶ÔÎ»ÖÃ·ÖËÄÖÖÇé¿ö if ( IsLChild( p ) ) // zig
//       if ( IsLChild( v ) ) { /* zig-zig */ /*DSA*/ // printf("\tzIg-zIg:
//       ");
//          p->parent = g->parent; //ÏòÉÏÁª½Ó
//          return connect34( v, p, g, v->lc, v->rc, p->rc, g->rc );
//       } else { /* zig-zag */ /*DSA*/ // printf("\tzIg-zAg: ");
//          v->parent = g->parent; //ÏòÉÏÁª½Ó
//          return connect34( p, v, g, p->lc, v->lc, v->rc, g->rc );
//       }
//    else // zag
//       if ( IsRChild( v ) ) { /* zag-zag */ /*DSA*/ // printf("\tzAg-zAg:
//       ");
//          p->parent = g->parent; //ÏòÉÏÁª½Ó
//          return connect34( g, p, v, g->lc, p->lc, v->lc, v->rc );
//       } else { /* zag-zig */  /*DSA*///printf("\tzAg-zIg: ");
//          v->parent = g->parent; //ÏòÉÏÁª½Ó
//          return connect34( g, v, p, g->lc, v->lc, v->rc, p->rc );
//       }
// }
template <typename T>
BinNodePosi<T> BST<T>::rotateGFS(BinNodePosi<T> a, BinNodePosi<T> b,
                                 BinNodePosi<T> c, BinNodePosi<T> t1,
                                 BinNodePosi<T> t2, BinNodePosi<T> t3,
                                 BinNodePosi<T> t4) {
  a->lc = t1;
  if (t1)
    t1->parent = a;
  a->rc = t2;
  if (t2)
    t2->parent = a;
  BinTree<T>::updateHeight(a);
  c->lc = t3;
  if (t3)
    t3->parent = c;
  c->rc = t4;
  if (t4)
    t4->parent = c;
  BinTree<T>::updateHeight(c);
  b->lc = a;
  a->parent = b;
  b->rc = c;
  c->parent = b;
  BinTree<T>::updateHeight(b);
  return b;
}
//                   b
//            a            c
//      1          2     3        4

template <typename T> BinNodePosi<T> BST<T>::rotate(BinNodePosi<T> son) {
  if (son == nullptr) {
    std::cout << "error! Fail to rotate a null node/n";
    exit(-1);
  }
  BinNodePosi<T> fa = son->parent;
  BinNodePosi<T> gf = fa->parent;
  if (IsLChild(fa)) {
    if (IsLChild(son)) {
      fa->parent = gf->parent;
      return rotateGFS(son, fa, gf, son->lc, son->rc, fa->rc, gf->rc);
    } else {
      son->parent = gf->parent;
      return rotateGFS(fa, son, gf, fa->lc, son->lc, son->rc, gf->rc);
    }
  } else {
    if (IsLChild(son)) {
      son->parent = gf->parent;
      return rotateGFS(gf, son, fa, gf->lc, son->lc, son->rc, fa->rc);
    } else {
      fa->parent = gf->parent;
      return rotateGFS(gf, fa, son, gf->lc, fa->lc, son->lc, son->rc);
    }
  }
}

#endif // !__BST_BASIC_
